For point-to-multipoint services (also denoted as one-to-many services) over systems such as the Internet Protocol (IP) multicast, the IP Data Casting (IPDC) and the Multimedia Broadcast/Multicast Services (MBMS), file delivery such as for instance the download of multimedia files is an important service.
However, many of the features for delivering files over point-to-point protocols, such as for instance the File Transfer Protocol (FTP) and the Hypertext Transfer Protocol (HTTP), are problematic for point-to-multipoint scenarios. In particular, the reliable delivery of files, that is the guaranteed delivery of files, using similar point-to-point acknowledgement (ACK) protocols such as the Transport Control Protocol (TCP) is not feasible.
The Reliable Multicast Transport (RMT) Working Group of the International Engineering Task Force (IETF) is currently in the process of standardizing two categories of error-resilient multicast transport protocols. In the first category, reliability is implemented through the use of (proactive) Forward Error Correction (FEC), i.e. by sending a certain amount of redundant data that can help a receiver in reconstructing erroneous data; in the second category, reliability is implemented through the use of receiver feedback.
Asynchronous Layered Coding (ALC) is a protocol instantiation belonging to the first category, while the NACK-Oriented Reliable Multicast (NORM) protocol belongs to the second category. The access networks on which these protocols could be used include, but are not limited to, wireless multiple-access networks such as the Universal Mobile Telecommunications System (UMTS, including the Global System for Mobile Communications Evolution Radio Access Network (GERAN) and the UMTS Terrestrial Radio Access Network (UTRAN)), Wireless Local Area Networks (WLAN), Digital Video Broadcasting-Terrestrial (DVB-T) networks and Digital Video Broadcasting-Satellite (DVB-S) networks.
Briefly, the ALC protocol is a proactive FEC-based scheme that allows receivers to reconstruct mangled packets or packets that have not been received. The ALC protocol uses FEC encoding on multiple channels, allowing the sender to send data at multiple rates (channels) to possibly heterogeneous receivers. Additionally, the ALC protocol uses a congestion control mechanism to maintain different rates on different channels.
The ALC protocol is massively scalable in terms of the number of users because no uplink signaling is required. Therefore, any amount of additional receivers does not exactly put increased demand on the system. However, the ALC protocol is not 100% reliable because reception is not guaranteed, thus it is generally not described as robust.
NORM, in turn, specifies the use of Negative Acknowledgement (NACK) messages in order to signal which data packets expected to arrive at the receiver were not received at the receiver at all, or were received incorrectly. In other words, receivers employ NACK messages to indicate loss or damage of transmitted data packets to the transmitter. Accordingly, a receiver that missed some data packets from a data transmission can send a NACK message to the transmitter (or a repair server) requesting the transmitter (or repair server) to re-transmit the missed data block or blocks. The NORM protocol also optionally allows for the use of data packet-level FEC encoding for proactive robust transmissions.
NACK messages are not generally NORM-specific, but they can also be used in connection with other protocols or systems, for instance with systems that support sessions that are controlled by the File Delivery over Unidirectional Transport (FLUTE) protocol.
FLUTE is a one-to-many transport protocol that builds on FEC and ALC building blocks. It is intended for file delivery from transmitter(s) to receiver(s) over unidirectional systems. It has specializations which make it suitable to wireless point-to-multipoint systems. The details of the FLUTE protocol are discussed in more detail in the publication entitled “FLUTE—File Delivery over Unidirectional Transport” (Internet Draft) prepared by the above-mentioned RMT Working Group of the IETF.
The use of FLUTE is for instance specified by the Third Generation Partnership Project (3GPP) for file download in sessions of the MBMS system. FEC may or may not have been used in such FLUTE sessions. In any case, not all receivers in the session can be expected to receive the whole file when the session ends. To this end, 3GPP is in the process of defining point-to-point repair sessions, wherein the receivers are allowed to signal requests for data packet re-transmissions to a transmitter or repair server via NACK messages in order to be able to reconstruct the downloaded content.
When using NACK messages in connection with FLUTE sessions (or in other sessions using a transport layer protocol especially directed to support point-to-multipoint transmission) the identification of the data packets missing at the receivers is an important issue. The usage of protocols intended for point-to-point transmission, such as TCP, and their acknowledgement methods are not necessarily feasible here.
In a FLUTE session, transport objects, for instance multimedia files or parts thereof, are identified by a Transport Identifier (TOI), and are transmitted from a transmitter to a plurality of receivers within a transport session, which is identified by a Transport Session Identifier (TSI). The transmission of said transport objects is actually performed by the transmission of FLUTE data packets, wherein the FLUTE data packets contain raw or coded portions of said transport object, so-called encoding symbols, as payload. Said FLUTE data packets further contain the TSI and TOI as well as an FEC Payload ID, which will be explained below.
Various FEC schemes specified by the RMT working group are based on a source block and encoding symbol structure. Such FEC schemes are described in RFC publication 3452 “Forward Error Correction Building Block” and RFC publication 3695 “Compact Forward Error Correction (FEC) Schemes”. Each encoding symbol can be identified by its Source Block Number (SBN) and its Encoding Symbol ID (ESI). All these FEC schemes assume that within each transport object, the SBN is sequentially increased by one, and that within a source block, the ESI is increased by one for each encoding symbol that is transmitted. Both SBN and ESI are contained in the FEC Payload ID that is contained in a FLUTE data packet.
In these FEC schemes, identification of FLUTE data packets that are not received at all or not received correctly at a receiver may be accomplished by their SBN and ESI, which are contained in the FEC Payload IF of FLUTE data packets. These parameters may then be signaled back as NACK to the transmitter to cause a re-transmission of these identified data packets.
However, publication “Simple Forward Error Correction (FEC) Schemes” (Internet Draft) by M. Luby introduces FEC schemes that use a simpler FEC Payload ID and can be used to deliver objects without using any explicit source block structure. These FEC Schemes may for instance use rate-less codes such as Luby Transform (LT) or Raptor codes.
An LT-encoder (see M. Luby, “LT-codes”, in Proceedings of the ACM Symposium on Foundations of Computer Science (FOCS), 2002) transmits a stream of encoded bits,
which are sparse random linear combinations of k data bits. The receiver picks up noisy versions of the encoded bits and uses a belief propagation decoder to try to figure out the k data bits. The number of noisy encoded bits n required for successful decoding depends on the quality and type of the channel. LT codes designed using the “robust soliton degree distribution” can achieve capacity on every binary erasure channel (BEC). In other words, R=k/n can be made arbitrarily close to (1−p) for every erasure probability p.
The key idea of Raptor Coding (see A. Shokrollahi, “Raptor codes”, Digital Fountain, Inc., Tech. Rep.
DF2003-06-001, June 2003) is to relax the condition that all input symbols need to be recovered. If an LT code needs to recover only a constant fraction of its input symbols, then its decoding graph need only have O(k) edges, allowing for linear time encoding. All input symbols can still be recovered by concatenating a traditional erasure correction code with an LT code. n intermediate symbols are then obtained by encoding k input symbols with an (k,n) erasure correcting block code capable of recovering all input symbols from a fixed fraction of intermediate symbols. The n intermediate symbols are then encoded with an LT code that can recover from its output symbols the required fraction of intermediate symbols.
The FEC Payload ID proposed for these FEC schemes consists of a 4 byte key from which the decoding graph is generated. The SBN is not included in this FEC Payload ID, and the ESI is meant to carry an identifier such as said 4 byte key in this case.
Moreover, the keys are randomly generated by the FEC encoder. Thus, the receiver may not be able to identify the missing data packets from the keys of the other data packets it has received in the session. As a result, identification of missing FLUTE data packets by their associated SBN and ESI is not applicable in these FEC schemes.